[BZOJ2469][中山市选2010]简单数谜

发表于 | 分类于 ， ， ， | | 阅读次数:

Description

很多人都曾经听说过数独，但你是否听说过数谜（Karuro）呢？实际上，数谜是数独的更大（且更难）的兄弟问题，而且在日本也是非常受欢迎的。
数谜问题和填字游戏类似，不过它要填的不是文字而是数字。数谜游戏的目标是用1-9填满所有空格，且这些数字相加的和满足相应的要求（或者称为“提示”），且在同一栏（“栏”是指一些水平或者竖直的连续的空格，用于提示的格子不算空格）不能填重复的数字。当所有格子按要求被填满后，这个数谜就看作被解决了。图1和图2是一个可能的数谜游戏示例。
当然，直接求解数谜问题的话会比较困难。所以现在我们需要解决的是一个更简单的数谜问题。简单数谜的形状是一个(n+1）行乘(m+1)列的矩形。而简单数谜也只有两种要求，就是行要求和列要求，且分别处于第一行和第一列，其他格子则是空格，而左上角是忽略不计的。coolzzz同学爱好简单数谜，他已经给一些简单数谜填好了其中的一些空格。现在，他想寻求你的帮助，来帮他完成这些简单数谜。如图3所示，2和9是coolzzz同学已经填好的空格，图4则是一个基于图3 的一个可能的解答。

Input

输入包含多组测试数据。第一行包含一个正整数T，表示测试数据数目。每组数据第一行是n(n<10)和m(m<10)，表示数谜的形状的大小。接下来一行有n个整数，是相应的行要求；然后一行是m个整数，是相应的列要求。接下来的n行每行有m个小于10的非负整数，0表示该空格还没有被填数字，其他表示coolzzz同学已经填好的数字。输入数据保证未填数字的空格不会超过16个。

Output

对于每组测试数据，输出若干行。如果基于coolzzz已填的结果，该数谜只有一个解，则输出该解；如果不止一个解，则输出一行“Not unique.”；如果没有解，则输出一行“No answer.”。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3
3 3
6 6 6
6 6 6
0 0 0
0 3 0
0 0 0
2 3
10 17
5 16 6
2 0 0
0 9 0
2 2
3 5
4 4
0 0
0 0

Sample Output

1
2
3
4
Not unique.
2 7 1
3 9 5
No answer.

题解

一道简单的爆搜题，和数独比起来稍微复杂一点（然而代码量更少），比较坑爹的就是如果不加一句话的话全部超时，加上去了就只要32ms
我们每次填只关心当前行满不满足要求，最后结束的时候再来判断是不是合法
具体数组作用可以用一个表格体现

数组（变量）名称 数组（变量）作用
ans 用来存放最终的结果
num 用来统计有多少个答案
kakuro 初始状态以及之后搜索时的状态
x,y 要求的行、列和
X,Y 当前行、列有哪些数是用过的
val_x,val_y 当前状态的行、列和

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=15;
int num;
int ans[MAXN][MAXN],kakuro[MAXN][MAXN];
int x[MAXN],y[MAXN];
bool Y[MAXN][MAXN],X[MAXN][MAXN];
int val_x[MAXN],val_y[MAXN];
int n,m;
 
inline void init(){
    cin>>n>>m;
    num=0;
    memset(ans,0,sizeof(ans));
    memset(kakuro,0,sizeof(kakuro));
    memset(val_x,0,sizeof(val_x));
    memset(val_y,0,sizeof(val_y));
    memset(X,0,sizeof(X));
    memset(Y,0,sizeof(Y));
    for(int i=1;i<=n;i++)cin>>y[i];
    for(int j=1;j<=m;j++)cin>>x[j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&kakuro[i][j]);
            Y[i][kakuro[i][j]]=1;
            X[j][kakuro[i][j]]=1;
            val_y[i]+=kakuro[i][j];
            val_x[j]+=kakuro[i][j];
        }
    }
}
 
inline void dfs(int now_x,int now_y){
    if(num>=2)return;
    if(now_y>n){
        bool ok=1;
        for(int i=1;i<=m;i++){
            if(val_x[i]!=x[i]){
                ok=0;
                break;
            }
        }
        if(ok){
            num++;
            memcpy(ans,kakuro,sizeof(kakuro));
        }
    }
    else if (now_x > m) {
        if (val_y[now_y] == y[now_y]) {//不加全超时
            dfs(1, now_y + 1);
        }
    }
    else if(kakuro[now_y][now_x]!=0)dfs(now_x+1,now_y);
    else {
        for(int i=1;i<=9;i++){
            if(!Y[now_y][i]&&!X[now_x][i]&&val_x[now_x]+i<=x[now_x]&&val_y[now_y]+i<=y[now_y]){
                Y[now_y][i]=X[now_x][i]=1;
                val_x[now_x]+=i;
                val_y[now_y]+=i;
                kakuro[now_y][now_x]=i;
                dfs(now_x+1,now_y);
                Y[now_y][i]=X[now_x][i]=0;
                val_x[now_x]-=i;
                val_y[now_y]-=i;
                kakuro[now_y][now_x]=0;
            }
        }
    }
}
 
inline void out(){
    if(num==0)printf("No answer.\n");
    else if(num==1){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                printf("%d ",ans[i][j]);
            }
            printf("\n");
        }
    }
    else {
        printf("Not unique.\n");
    }
}
 
int main(){
//   freopen("poi.out","w",stdout);
    int t;
    cin>>t;
    int T=t;
    while(t--){
        // printf("Case %d:\n",T-t);
        init();
        dfs(1,1);
        out();
    }
    return 0;
}